Pearls in Graph Theory by Nora Hartsfield & Gerhard Ringel

Author:Nora Hartsfield & Gerhard Ringel
Language: eng
Format: epub, pdf
Publisher: Dover Publications
Published: 1994-06-22T16:00:00+00:00

Notice that if we add the same number, for example 100, to every label in Figure 6.2.4, Kirchhoff’s Current Law still holds at every vertex. If we try this with Figure 6.2.2, it will not work. This leads us to the following definition. A graph G with q edges is called strongly conservative if for every number h there exists a directed labeling of the edges of G with the numbers h+l, h+2,..., h+q such that Kirchhoff’s Current Law holds at every vertex. Thus the graph in Figure 6.2.4 is strongly conservative, while the graph in Figures 6.2.1 and 6.2.2 may or may not be strongly conservative. We cannot say at the moment.

The proof of the following theorem is actually easier than the proof of the corresponding theorem for magic graphs.

Theorem 6.2.3. If G is decomposable into two subgraphs H1 and H2, and if H1 is conservative, and H2 is strongly conservative, then G is conservative. Moreover, if both H1 and H2 are strongly conservative, then G is strongly conservative.

Proof. Let q1 be the number of edges in H1 and q2 the number of edges in h2, so the number of edges in G is q1 + q2. Take a conservative labeling of h1using the numbers 1, 2, 3,..., q1 and a strongly conservative labeling of h2 using the numbers q1 + 1, q1 + 2,..., q1 + q2. In both these labelings Kirchhoff’s Current Law holds, so the directed sum at each vertex is zero in G. Hence we have exhibited a conservative labeling of G.

Now we suppose that both H1 and H2 are strongly conservative, and h is a given number. Take a strongly conservative labeling of the edges of H1 using the numbers h + 1, h + 2,..., h + q1, and a strongly conservative labeling of the edges of H2 using the numbers h +q1 + 1, h + q1 + 2,..., h + q1 + q2. Again, the directed sum at each vertex is zero, and we obtain a strongly conservative labeling of the edges of G using the numbers h + 1, h + 2,..., h + q1 + q2. Thus G is strongly conservative.

Notice that the graph of Theorem 6.2.1 is actually strongly conservative, since the conservative labeling consists of two edges directed in and two edges directed out at each vertex. Hence, adding a constant h to the label of each edge does not affect the directed sum at each vertex.

Theorem 6.2.1*. If G is decomposable into two Hamilton cycles, then G is strongly conservative.

Theorem 6.2.4. If G is a graph with n vertices, where n is odd, and G is decomposable into three Hamilton cycles, then G is strongly conservative.

Proof. Call the three Hamilton cycles H1, H2, and H3. We direct the edges of each of H1, H2, and H3 in such a way that a traveler going around one of these cycles finds all the arrows going in the same direction. See Figures 6.2.5 and 6.2.6. We choose a vertex a and label the edges of H3, beginning at a, by

(H3)a 3n, 3n−6,.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.